package leetcode.code295;

import java.util.PriorityQueue;

public class MedianFinder2 extends Solution295 {

	private PriorityQueue<Integer> min;
	private PriorityQueue<Integer> max;

	public MedianFinder2() {
		min = new PriorityQueue<>((o1, o2) -> o1 - o2);
		max = new PriorityQueue<>((o1, o2) -> o2 - o1);
	}

	@Override
	public void addNum(int num) {
		if (min.size() == 0) {
			min.add(num);
			return;
		}
		if (num > min.peek()) {
			min.add(num);
		} else {
			max.add(num);
		}
		if (min.size() - max.size() == 2) {
			max.add(min.poll());
		} else if (max.size() - min.size() == 2) {
			min.add(max.poll());
		}
	}

	@Override
	public double findMedian() {
		if (min.size() - max.size() == 0) {
			return (max.peek() + min.peek()) / 2.0;
		}
		if (min.size() - max.size() == 1) {
			return min.peek();
		}
		if (max.size() - min.size() == 1) {
			return max.peek();
		}
		return 0;
	}

	public static void main(String[] args) {
		MedianFinder2 medianFinder = new MedianFinder2();
//		medianFinder.debug1();
		medianFinder.debug2();
	}

}
